1. Field of the Invention
The present invention relates to data transfer systems. In particular, the invention relates to an error-correcting method, an error-checking device, a decoding method and a decoder applied to a system for error correction and check of a multidimensional code such as a product code.
2. Description of the Background Art
Image information and the like containing a large amount of information are now recorded, reproduced and transmitted by digital signals in most instances. Accordingly, there arises an increased importance of error correction and error check in order to enhance the reliability of recorded information or transmitted information. Especially real-time recording and reproduction requires high-speed processing for correcting and checking any error in such a large amount of information.
A conventional data transfer system, for example, a recordable and reproducible magneto-optical disk device adds an error-correcting code formed of a product code to received data and stores the data on a recording medium.
The stored data is thereafter called by an error-correcting device as required and any error is corrected. Error check is then carried out by an error detecting code (hereinafter referred to as EDC) to confirm absence of errors, and the data is output to the outside.
In a reproduction-only optical disk device, stored data is similarly called as required by an error-correcting device where any error is corrected. Error check is thereafter performed by an error detecting code to confirm absence of errors. The data is then output to the outside.
According to a conventional error-correcting method, data read from a DVD (Digital Versatile Disk) for example is temporarily stored in a buffer of an external semiconductor memory device such as a Synchronous Dynamic Random Access Memory (SDRAM). The data is then called by an error-correcting device to correct any error.
The DVD employs for example a product code constituted of data arranged in a rectangular shape to which error-correcting codes are added in two directions, i.e., the vertical direction (PO direction) and the horizontal direction (PI direction).
FIG. 32 shows a format of a conventional error-correcting product code for the DVD.
Here, one block refers to data formed of information data arranged in two-dimension in 172 bytesxc3x97192 rows to which horizontal 10-byte parity PI (error-correcting inter code) and vertical 16-byte parity PO (error-correcting outer code) are added. The horizontal and vertical directions are also called PI and PO directions respectively in FIG. 32.
FIG. 33 shows a relation between the error-correcting product code (error-correcting inter code and error-correcting outer code) in FIG. 32 and error detecting codes (EDC).
One block mentioned above is divided into sixteen sectors each consisting of data arrangement in 172 bytesxc3x9712 rows. One sector includes a 4-byte EDC at its end.
FIG. 34 shows data arrangement in one sector containing the error detecting code. The bits are numbered in descending order from the leading bit.
The one-sector data are arranged as data from bit data b16511 to bit data b0 and bit data b31 to b0 correspond to the EDC.
FIG. 35 is a schematic block diagram illustrating a first conventional structure for error correction and error check applied to the DVD data structured as discussed above.
Referring to FIG. 35, a basic decoding pattern follows the procedure for example described below.
1. An input signal is stored in a data buffer (SDRAM: Synchronous Dynamic Random Access Memory) 3024 via a data bus 3021, and a PI direction error-correcting circuit 3020 reads data in PI direction from data buffer 3024 to calculate a syndrome.
2. PI direction error-correcting circuit 3020 detects an error amount and an error position from the value of the PI direction syndrome to correct any error in the data stored in data buffer 3024.
3. A PO direction error-correcting circuit 3022 reads data in PO direction from data buffer 3024 to calculate a syndrome.
4. PO direction error-correcting circuit 3022 calculates an error amount and an error position from the value of the PO direction syndrome to correct any error in the data stored in data buffer 3024.
These processes are repeated to correct errors.
5. After the error correction is completed, an error-checking circuit 3023 reads the data from data buffer 3024 to confirm absence of errors by using error detecting codes.
A problem here in these processes is that the error correction and check takes a long time since, after error correction, data buffer (SDRAM) 3024 is accessed again for error check.
For example, in the structure shown in FIG. 35, only after error correction of data read from data buffer 3024 is completed, error-checking circuit 3023 reads the data from data buffer 3024. Relatively time-consuming data reading and writing from and to data buffer 3024 is carried out frequently, resulting in a longer time taken by the processes.
Japanese Patent Laying-Open No. 11-55129 for example discloses a method to overcome this problem.
FIG. 36 is a schematic block diagram illustrating a second conventional structure for error correction and error check disclosed in Japanese Patent Laying-Open No. 11-55129.
The error-correcting and checking device shown in FIG. 36 is structured to use a data bus shared by an error-correcting circuit and an error-checking circuit.
FIGS. 37, 38, 39 and 40 respectively show first to fourth models illustrating a general process followed by the error-correcting and checking device shown in FIG. 36.
In FIGS. 37 and 38, data to be error-checked are shown in a decreased number, i.e., 40 data (10 columnsxc3x974 rows) for the purpose of simplifying illustration.
Error check by means of the error-correcting and checking device shown in FIG. 36 is carried out in two stages.
In the first stage, data is read from a buffer 3034 for error correction in PI direction for example, and the data is transferred in the data arrangement order as shown in FIG. 37 to a DATA syndrome generating circuit 3036 to calculate a DATA syndrome.
The calculated DATA syndrome is stored in a memory device 3032.
In the first stage, in addition to the DATA syndrome calculation, an ERROR syndrome is calculated by using an error amount detected by a PI direction error-correcting circuit 3030 according to the data arrangement order shown in FIG. 37.
In the second stage, an error amount detected by a PO direction error-correcting circuit 3032 is further used to perform subsequent ERROR syndrome calculation according to the data arrangement order shown in FIG. 38.
Referring to FIG. 39, an exclusive-OR operation unit 3035 calculates the exclusive-OR of the two syndromes, DATA syndrome and ERROR syndrome, so as to determine a final check syndrome. Based on the check syndrome, a decision circuit 3031 judges results of error check.
The second-time data reading from data buffer 3034 for generating a check syndrome is thus unnecessary so that fast and parallel error correction and check processes are possible.
Further, in the calculation of the error-correction syndrome by PO direction error-correcting circuit 3032, if codewords in column 3 (COL3) have no error, subsequent detection of an error amount and an error position is skipped. According to this, in the ERROR syndrome calculation, the speed of operation is enhanced by using offset values for the codewords without error as shown in FIG. 40.
However, this offset calculation requires, in ERROR syndrome generating circuit 3038, an operating circuit having at least three paths for syndrome calculation corresponding respectively to an operation proceeding through rows one by one in the vertical direction, an operation through columns from one column to the next column, and an operation through columns at every other columns. A problem then arises of increase in the circuit scale.
Other problems of syndrome calculation in the error-correcting operation are discussed below.
The conventional error-correcting system such as DVD uses a product code as described above having data arranged in the rectangular shape to which error-correcting codes are added in the vertical and horizontal directions.
FIG. 41 is a schematic block diagram showing a structure of a conventional error-correcting device 4000 for the error-correcting calculation as discussed above.
Referring to FIG. 41, in error-correcting device 4000, data read into an external memory 4021 undergoes error correction by an error-correcting circuit 4022.
Error-correcting circuit 4022 reads the data from external memory 4021 for correcting any error and then the data with its error corrected is written into external memory 4021 again.
After all errors are corrected, a descramble operation is performed by a descrambling circuit 4023.
Descrambling circuit 4023 reads the data from external memory 4021 to descramble the data and the descrambled data is written into external memory 4021 again.
Specifically, a basic decoding pattern follows the procedure below.
1. PI direction data is read from external memory (e.g. SDRAM) 4021 to calculate a syndrome.
2. An error amount and an error position are calculated from the syndrome value to correct any error on external memory 4021.
3. PO direction data is read from external memory 4021 to calculate a syndrome.
4. An error amount and an error position are calculated from the syndrome value to correct any error in data stored on external memory 4021.
These processes are repeated to accomplish error correction.
5. After this error correction, data (Dxe2x80x2k: data produced by scrambling data Dk is hereinafter represented by Dxe2x80x2k) is read from external memory 4021 again to descramble the data by descrambling circuit 4023 according to the following expression.
Dk=Dxe2x80x2k Exor Sk(k=0xe2x88x922047)xe2x80x83xe2x80x83(A1) 
Here, S0 is supplied as an initial value by a table provided in advance. Further, data Sk derived from the following expressions is used to descramble data Dxe2x80x2k.
T0={7xe2x80x2d0, S0}xe2x80x83xe2x80x83(A2) 
Tn+1[14:0]={Tn[13:1], (Tn[14]Exor Tn[10])}xe2x80x83xe2x80x83(A3) 
(n=0xe2x88x928xc3x972047) 
Sk=T8k[7:0]xe2x80x83xe2x80x83(A4) 
In expression (A2), xe2x80x9c7xe2x80x2d0xe2x80x9d means there are seven data xe2x80x9c0xe2x80x9d that are lined. Expression (A2) represents that seven xe2x80x9c0xe2x80x9d and S0 as the initial value are connected to form data T0 of 15 bits from the 14th bit to the 0th bit.
Expression (A3) represents that data Tn [13:0] from the 13th bit to the 0th bit in data Tn [14:0] generated in the n-th step is lined next to the exclusive-OR of the 14th bit data Tn [14] and the tenth bit data Tn [10] in data Tn [14:0] to generate in the (n+1)-th step data Tn+1 [14:0] formed of 15-bit data from the 14th bit to the 0th bit.
Expression (A4) represents that in the data Tn [14:0] thus generated the data of the 7th bit to the 0th bit in the data T8k [14:0] formed in the 8-multiple-th step corresponds to data Sk.
The access to the external memory is enormous in the circuit structure shown in FIG. 41, which consumes a longer time and accordingly makes it difficult to enhance the speed of error correction and descrambling.
A conventional art for overcoming such a problem is described below.
FIG. 42 is a schematic block diagram showing a structure of an error-correcting device 5000 as such a conventional art that is disclosed in Japanese Patent Laying-Open No. 10-126279.
Referring to FIG. 42, for data read into an external memory 5031, syndrome calculation is performed by a syndrome operating circuit 5032 as a part of error-correcting calculation.
At the same time, the read data is sent to a descrambling circuit 5033 to be descrambled. The descrambled data is written into external memory 5031.
A syndrome determined by the syndrome calculation is supplied to an error amount calculating unit 5034 to calculate an error amount and an error position. Error amount calculating unit 5034 reads data corresponding to the error position from external memory 5031, corrects any error, and the data is written into external memory 5031 again.
Although this method reduces the access to the external memory approximately by two thirds, this reduction is not enough.
Further, the method considers nothing about the repeating processes specific to the product code. Therefore, efficient error correction/descrambling for the actual DVD and the like is difficult to achieve.
Specifically, error correction of the product code is generally performed in each of the directions (PO and PI directions) repeatedly. Here, syndrome calculation for performing error correction uses data before descrambling. If descrambling as shown in FIG. 42 is employed, data stored in external memory 5031 must be scrambled again in order to perform subsequent error correction repeatedly, resulting in increase in the calculation amount and circuit scale.
Problems of Euclidean calculation in the error-correcting operation are described below.
FIG. 43 is a schematic block diagram showing a structure of an error-correcting device 6000 in a conventional data transmission system, for example, a recordable and reproducible magneto-optical disk device.
Referring to FIG. 43, the data transmission system adds an error-correcting code formed of a product code to data to be recorded and stores the data on a recording medium. The data stored on the recording medium is then supplied as received data to error-correcting device 6000 as required and thereafter output to the outside after error correction.
Such a structure is employed not only in the recordable and reproducible magneto-optical disk device but also in a reproduction only optical disk device.
An error-correcting process is discussed below carried out in a DVD for example. The DVD employs error correction by a Reed-Solomon code (RS code) exhibiting a high correcting ability.
Received data called for transmission from a disk to error-correcting device 6000 is temporarily stored in a semiconductor memory device, specifically memory 6010 such as an SRAM (Static Random Access Memory). The data in memory 6010 is thereafter called for the error-correcting process in which the following procedure steps are successively followed.
The five steps below are generally employed for error correction using the Reed-Solomon code.
1. A syndrome calculating circuit 6020 calculates a syndrome from the received data.
2. A Euclidean calculating circuit 6030 determines an error locator polynomial and an error evaluator polynomial from that syndrome.
3. A Chien search circuit 6040 determines an error position from the error locator polynomial.
4. Chien search circuit 6040 determines an error amount from the error locator polynomial, error evaluator polynomial and error position.
5. An error-correcting circuit 6050 corrects any error using the error amount and position.
Regarding the error correction by the Reed-Solomon code having a high correction ability, a Euclidean method derived from the Euclidean algorithm is known that is used in step 2 above for determining the error locator polynomial and the error evaluator polynomial from the syndrome.
This Euclidean method is now described in detail below.
A reception polynomial r (x) of the received data described above is represented here by the expression below:
r(x)=rnxe2x88x921xnxe2x88x921+rnxe2x88x922xnxe2x88x922+. . . +r1x+r0xe2x80x83xe2x80x83(B1) 
where n is a code length.
A syndrome polynomial determined by syndrome calculation is represented as below.
S(x)=S2txe2x88x921x2txe2x88x921+S2txe2x88x922x2txe2x88x922+. . . +S1x+S0xe2x80x83xe2x80x83(B2)                               S          j                =                              ∑            i                    ⁢                                    r              i                        ⁢                          α                              j                xc3x97                i                                      ⁢                          xe2x80x83                        ⁢                          (                                                i                  =                  0                                ,                …                ⁢                                  xe2x80x83                                ,                                  n                  -                  1                                ,                                  j                  =                  0                                ,                …                ⁢                                  xe2x80x83                                ,                                                      2                    ⁢                    t                                    -                  1                                            )                                                          (B3)            
In the expressions above, t denotes the number of correctable errors and xcex1 denotes the root of a primitive polynomial on GF (P). With respect to GF (28), roots in a root set of the primitive polynomial are expressed by 0, 1, xcex11, xcex12, xcex16.
Error locator polynomial "sgr" (x) is defined here by the following expression:                               σ          ⁡                      (            x            )                          =                              ∏                          i              ∈              E                                ⁢                      (                          x              -                              α                                  -                  li                                                      )                                              (B4)            
where E denotes a set of errors, i denotes an element of set E, and li denotes an error position.
The syndrome polynomial and error locator polynomial "sgr" (x) have the relation determined as shown below.
"sgr"(x)xc2x7S(x)xe2x89xa1xcfx89(x)mod x2txe2x80x83xe2x80x83(B5) 
In expression (B5), error evaluator polynomial xcfx89 (x) is a polynomial as written below.                               ω          ⁡                      (            x            )                          =                              ∑                          i              ∈              E                                ⁢                                                    e                i                            ·                              α                                  -                  li                                                      ⁢                                          ∏                                                      j                    ≠                    i                                                        j                    ∈                    E                                                              ⁢                              (                                  x                  -                                      α                                          -                      lj                                                                      )                                                                        (B6)            
Similarly, j denotes an element of set E and lj denotes an error position.
Alternatively, expression (B5) is written by an equivalent expression below.
xcfx86(x)xc2x7x2t+"sgr"(x)xc2x7S(x)=xcfx89(x)xe2x80x83xe2x80x83(B7) 
Expression xcfx86 (x) is represented as follows.                               φ          ⁡                      (            x            )                          =                              ∑                          i              ∈              E                                ⁢                                                    e                i                            ·                              α                                                      li                    ·                    2                                    ⁢                  t                                                      ⁢                                          ∏                                                      j                    ≠                    i                                                        j                    ∈                    E                                                              ⁢                              (                                  x                  -                                      α                                          -                      lj                                                                      )                                                                        (B8)            
Euclidean decoding algorithm is a method of determining error locator polynomial "sgr" (x) and error evaluator polynomial xcfx89 (x) based on relation (B7) above.
Specifically, when the number of errors is equal to t or less, error locator polynomial "sgr" (x) and error evaluator polynomial xcfx89 (x) can uniquely be determined from expression (B7) by Euclidean algorithm to determine the greatest common divisor polynomial of x2t and S (x).
Brief description is given below concerning a procedure of determining error locator polynomial "sgr" (x) and error evaluator polynomial xcfx89 (x) from expression (B7).
According to this procedure, polynomial "sgr" (x) with degree t or lower and polynomial xcfx89 (x) with degree (txe2x88x921) or lower, which satisfy expression (B7) and are prime to each other, are determined.
Recurrence formula of polynomials Zi (x) is represented as shown below.
Zxe2x88x921(x)=x2t, Z0(x)=S(x)xe2x80x83xe2x80x83(9) 
Based on expression (B9), polynomials Xi (x), Yi (x) and Zi (x) satisfying expression (B10) below are successively generated and this operation is repeated until Yi (x) has degree t or lower and Zi (x) has degree (txe2x88x921) or lower.
Xi(x)Zxe2x88x921(x)+Yi(x)Z0(x)=Zi(x)xe2x80x83xe2x80x83(B10) 
It can be proved that polynomials Yi (x) and Zi (x) thus generated correspond to error locator polynomial "sgr" (x) and error evaluator polynomial xcfx89 (x), except for multiples of a constant. The following explanation assumes that such a correspondence is established.
Respective initial values of Xi (x) and Yi (x) are expressed as shown below.
Xxe2x88x921(x)=1, X0(x)=0xe2x80x83xe2x80x83(B11) 
Yxe2x88x921(x)=0, Y0(x)=1xe2x80x83xe2x80x83(B12) 
For i=xe2x88x921, 0, it is apparent that expression (B10) is satisfied.
However, since Zxe2x88x921 (x)=x2t is a polynomial of degree t or higher and the degree of S (x) is at least t as long as the number of errors is t or less, Z0 (x)=S (x) is a polynomial of degree t or higher. Therefore, Zxe2x88x921 (x) and Z0 (x) are never error evaluator polynomial xcfx89 (x).
In the following process, the degree of Zi (x) is decreased with expression (B10) being satisfied.
It is assumed here that following expressions (B13) and (B14) are satisfied for i (xe2x89xa71).
Xixe2x88x922(x)Zxe2x88x921(x)+Yixe2x88x922(x)Z0(x)=Zixe2x88x922(x)xe2x80x83xe2x80x83(B13) 
Xixe2x88x921(x)Zxe2x88x921(x)+Yixe2x88x921(x)Z0(x)=Zixe2x88x921(x)xe2x80x83xe2x80x83(B14) 
Zixe2x88x921 (x) is lower in degree than Zixe2x88x922 (x).
The degree can be lowered based on expressions (B13) and (B14). Zixe2x88x922 (x) is divided by Zixe2x88x921 (x) and the resultant quotient is here denoted by Qi (x). Members on both sides of expression (B14) are multiplied by Qi (x), and resultant products are subtracted from both members of expression (B13).
This corresponds to the following expressions in which Xi (x), Yi (x) and Zi (x) are represented as shown below based on expressions (B13) and (B14).
Zi(x)=Zixe2x88x922(x)xe2x88x92Qi(x)Zixe2x88x921(x)xe2x80x83xe2x80x83(B15) 
Xi(x)=Xixe2x88x922(x)xe2x88x92Qi(x)Xixe2x88x921(x)xe2x80x83xe2x80x83(B16) 
Yi(x)=Yixe2x88x922(x)xe2x88x92Qi(x)Yixe2x88x921(x)xe2x80x83xe2x80x83(B17) 
If expressions (B13) and (B14) are satisfied, then expression (B10) is satisfied for polynomials Xi (x), Yi (x) and Zi (x) that satisfy expressions (B15) to (B17).
Zi (x) corresponds to the remainder determined by dividing Zixe2x88x922 (x) by Zixe2x88x921 (x), therefore, the degree thereof is lower than that of Zixe2x88x921 (x). The operation of expression (B15) is exactly the process of Euclidean algorithm to determine the greatest common divisor of x2t and S (x) in expression (B9).
FIG. 44 is a flowchart illustrating a flow of process for determining error locator polynomial "sgr" (x) and error evaluator polynomial xcfx89 (x) by such Euclidean algorithm.
FIG. 44 shows a decoding algorithm for (182, 172, 11) RS code for example.
The Euclidean algorithm is applied for determining the greatest common divisor of expression x2txc3x97x10 and syndrome polynomial S (x) below.
S(x)=S9x9+S8x8+S7x7+S6x6+S5x5+S4x4+S3x3+S2x2+S1x1+S0xe2x80x83xe2x80x83(B18) 
Referring to FIG. 44, calculation starts for determining error locator polynomial "sgr" (x) and error evaluator polynomial xcfx89 (x) by Euclidean algorithm (step S10) and an initial value is set.
Variable R0i (i=0, 1, . . . , 10) is set as shown below corresponding to coefficient of x10.
R010=1, R0i=0 (i=0, 1, . . . , 9)
Variable R1i (i=0, 1, . . . , 9) is set as below corresponding to coefficient of S (x).
R1i=Si (i=0, 1, . . . , 9)
Further, variables B0i, B1i (i=0, 1, . . . , 5) are set as below corresponding to respective coefficients of Yxe2x88x921 (x) and Y0 (x).
B0i=0 (i=0, 1, . . . , 5)
B1i=0 (i=1, . . . , 5), B10=1
The initial setting is now completed (step S12).
The degree of a polynomial having coefficient R0i is determined as N0 and the highest-degree coefficient of the polynomial is determined as Q0. Further, the degree of a polynomial having coefficient R1i is determined as N1 and the highest-degree coefficient of the polynomial is determined as Q1 (step S14).
N1 and 0 are compared (step S16). If N1=0, this process ends (step S30). If N1 is not equal to 0, the process proceeds to the next step.
After DN=N0xe2x88x92N1 operation, flag variable FN is set to 1 if DN less than 0 and to 0 if DNxe2x89xa70 (step S18).
Flag variable FN and 0 are compared and the process proceeds to step S22 if FN=0 and to step S28 if FN=1 (step S20).
In step S20, the following operation is performed if FN=0.
R1i=Q0*R1(ixe2x88x92DN)(i=0, 1, . . . , 9)
R0i=Q1*R0i (i=0, 1, . . . , 9)
R110=0
B1i=Q0*B1(ixe2x88x92DN)(i=0, 1, . . . , 5)
B0i=Q1*B0i (i=0, 1, . . . , 5)
Operation * represents multiplication on an element on a Galois field. If (ixe2x88x92DN) is negative, 0 is assigned to R1i and B1i in the left side member (step S22).
The following operation is further performed on coefficients.
R0i=R0i exor R1i (i=0, 1, . . . , 9)
B0i=B0i exor B1i (i=0, 1, . . . , 5)
Operation exor represents exclusive-OR operation (step S24).
Decision is made on whether the degree of polynomial R0x expressed by variable R0i is equal to t (5 in this example) or lower (step S26). If the degree of polynomial R0x is equal to or lower than t, this process ends (step S30). If not, the process proceeds to step S28.
If FN=0 is not satisfied in step S20 or the degree of polynomial R0x is greater than t in step S26, values of variables R0i and R1i are exchanged with each other and values of variables B0i and B1i are exchanged with each other. After such exchange, the process returns to step S14 (step S28).
Calculation by Euclidean algorithm by another Reed-Solomon code or BCH code (Bose-Chaudhuri-Hpcquenghem code) in more general case is similarly done.
This calculation requires a multiplier of a Galois field dedicated to operation xe2x80x9c*xe2x80x9d.
However, a problem here is the need of many multipliers for fast processing. In other words, although the greater number of multipliers increase the circuit size, an enhanced processing rate is achieved.
Reduction of the times multiplication is performed is also necessary, since power consumption increases if multiplication is carried out many times.
As an example, when the conventional circuit structure for implementing the Euclidean method discussed above employs one multiplier and the algorithm shown in FIG. 44 is followed therein, the circuit scale and throughput are estimated as below.
Number of multipliers: 1
Number of steps required for multiplication: 2xc3x972txc3x972t
Number of times multiplication is performed: 2xc3x972txc3x972t
A problem arises that, since the number of steps is proportional to the square of t, an increased t makes it impossible to enhance the processing rate.
Japanese Patent Laying-Open No. 1-276825 discloses a circuit structure for achieving fast calculation for such Euclidean method.
According to Japanese Patent Laying-Open No. 1-276825, speed enhancement of Euclidean calculation is accomplished by providing one multiplier per register.
For example, when the number of correctable errors is t, the minimum number of necessary registers is (2t+1). The circuit scale and throughput of the circuit structure disclosed in Japanese Patent Laying-Open No. 1-276825 are estimated as follows.
Number of multipliers: 2xc3x97(2t+1)
Number of steps required for multiplication: 2t
Number of times multiplication is performed: 2xc3x972txc3x972t
Although speed enhancement is accomplished here, numerous multipliers are used and accordingly the circuit scale cannot be reduced.
Japanese Patent Laying-Open No. 10-65552 for example discloses another circuit structure for speedily performing such Euclidean calculation.
According to Japanese patent Laying-Open No. 10-65552, four multipliers are provided for example for improving the calculation speed in the Euclidean method.
For example, when the number of correctable errors is t, the circuit scale and throughput of the circuit structure disclosed in Japanese Patent Laying-Open No. 10-65552 are estimated as follows.
Number of multipliers: 4
Number of steps required for multiplication: 2txc3x972t
Number of times multiplication is performed: 2xc3x972txc3x972t
Here again, since the number of steps is proportional to the square of t, the processing rate cannot be enhanced if the value of t increases.
In addition, power consumption is difficult to reduce in the conventional circuit structures discussed above due to the number of multiplying operations, i.e., xc3x972txc3x972t.
One object of the present invention is to provide an error-correcting device to achieve reduction in the time required for error check by shortening the access time to a memory device and performing the error check in parallel with error correction without increasing the circuit scale.
Another object of the invention is to provide a decoder capable of speedily perform error correction and descrambling of a product code.
Still another object of the invention is to provide an error-correcting device and an error-correcting method to achieve reduction in the time required for Euclidean processing without increase in the circuit scale resulting from an increased number of multipliers.
A further object of the invention is to provide an error-correcting device and an error-correcting method to achieve reduction in the power consumption of the circuit by reducing the number of multiplying operations in Euclidean processing.
According to one aspect of the invention, the present invention is, in brief, an error-correcting device including an error-correction operating unit, a first storage element and an error-checking unit.
The error-correction operating unit performs error correction on data to be corrected including an error-correcting code. The error-correcting code has a product code enabling error correction in first and second directions of a data block. The error-correction operating unit includes first and second error-correcting units. The first error-correcting unit is used for correction in the first direction of the product code. The second error-correcting unit is used for correction in the second direction.
The first storage element can store data to be corrected.
The error-checking unit performs error check by error detecting codes for confirming the correction by the error-correction operating unit. The error detecting codes are provided successively in the first direction of the data block. The error-checking unit includes a first logic operation unit and first and second direction error-checking units. The first logic operation unit uses an error amount detected by the error correction in the first direction and data stored in the first storage element to calculate a first error check result. The first-direction error-checking unit according to the first error check result performs error check after the error correction in the first direction. The second direction error-checking unit uses an error amount detected in the error correction in the second direction, calculates a second error check result and performs logical operation on the first and second error check results to perform error check after the error correction in the second direction.
According to another aspect of the invention, an error-correcting method includes the steps of: receiving data to be corrected including an error-correcting code having a product code enabling error correction in first and second directions of a data block to perform error correction in the first direction; receiving the data to be corrected to perform error correction in the second direction, using successively the data before error correction and an error amount detected by the error correction in the first direction to calculate a first error check result; performing error check after the error correction in the first direction according to the first error check result; and using an error amount detected in the error correction in the second direction, calculating a second error check result and performing a logical operation on the first and second error check results to perform error check after the error correction in the second direction.
According to still another aspect of the invention, a decoder for data including an error-correcting product code includes a control unit, a first storage element, an error-correcting unit, and a descrambling unit.
The control unit controls an operation of the decoder. The first storage element temporarily stores transmitted data. The error-correcting unit performs error correction on the data read into the first storage element. The descrambling unit descrambles the data stored in the first storage element. The control unit causes the error-correcting unit to perform error correction on the data read into the first storage element to transfer the error-corrected data to the descrambling unit where the error-corrected data is descrambled and thereafter written back into the first storage element.
According to a further aspect of the invention, a decoder includes a control unit, a first storage element, a first error-correcting unit, a descrambling unit and a second error-correcting unit.
The control unit controls an operation of the decoder. The first storage element temporarily stores transferred data including an error-correcting product code. The first error-correcting unit performs error correction in a first-direction on data read from the first storage element. The descrambling unit descrambles the data. The second error-correcting unit receives a first direction error-correction result to perform error correction in the second direction.
The controller causes, i) after error correction in the first direction on the data read from the first storage element, the descrambling unit to descramble the data having been subjected to the first direction error correction, ii) the descrambled data to be written back into the first storage element, and iii) in parallel with descrambling, the second error-correcting unit to perform error correction on the data stored in the first storage element to be written back into the first storage element.
According to a further aspect of the invention, a Euclidean calculating unit includes a first storage unit, a second storage unit, a control unit, a multiplier, a selector and a logical operation unit.
The first storage unit stores, in an operation for serially deriving coefficients of an error evaluator polynomial indicating an error amount of received data, first data corresponding to the coefficients of the error evaluator polynomial and the first storage unit can shift the first data. The second storage unit stores, in an operation for serially deriving coefficients of an error locator polynomial indicating an error position of the received data based on Euclidean algorithm, second data corresponding to the coefficients of the error locator polynomial, and the second storage unit can shift the second data. The control unit performs, based on a syndrome polynomial corresponding to the received data, initial setting of the data stored in the first and second storage units and controls Euclidean algorithm processing. The multiplier is provided commonly to the first and second storage units to perform multiplication on a Galois field based on the Euclidean algorithm. The selector controlled by the control unit controls data transfer between the multiplier and the first and second storage units. The logic operation unit performs a logical operation on the data stored in the first and second storage units based on the Euclidean algorithm.
According to a further aspect of the invention, a Euclidean calculating unit includes a first evaluation polynomial storage unit, a second evaluation polynomial storage unit, a control unit, a storage unit, a multiplier, a logic operation unit and an exchanging unit.
The first evaluation polynomial storage unit stores, for serially performing operations for deriving coefficients of an error evaluator polynomial indicating an error amount of received data based on Euclidean algorithm, first coefficient data in course of the operations. The second evaluation polynomial storage unit stores second coefficient data in course of the operations for deriving the coefficients of the error evaluator polynomial and can shift the second coefficient data. The control unit performs initial setting of the first and second coefficient data based on a syndrome polynomial corresponding to the received data, and controls Euclidean algorithm processing. The storage unit stores a multiplication result of a highest-degree coefficient of a first polynomial corresponding to the first coefficient data and a reciprocal of a highest-degree coefficient of a second polynomial corresponding to the second coefficient data. The multiplier multiplies each of the second coefficient data shifted by a difference between respective degrees of the first and second polynomials by the second evaluation polynomial storage unit by an output of the storage unit, and stores again a multiplication result as the second coefficient data in the second evaluation polynomial storage unit. The logical operation unit performs logical operation on the second coefficient data stored again by the multiplier in the second evaluation polynomial storage unit and the first coefficient data stored in the first evaluation polynomial storage unit, and stores operation result as the first coefficient data in the first evaluation polynomial storage unit. The exchanging unit exchanges the data stored respectively in the first and second evaluation polynomial storage units when the first polynomial corresponding to the first coefficient data has a degree higher than a predetermined degree or the first polynomial has its degree higher than a degree of the second polynomial. The control unit decides that the first polynomial is the error evaluator polynomial when the first polynomial has its degree lower than the predetermined degree.
According to a further aspect of the invention, an error-correcting method includes the steps of determining, based on a syndrome polynomial corresponding to received data, an error locator polynomial indicating an error position and an error evaluator polynomial indicating an error amount by a Euclidean method, and performing error correction on the received data.
The step of determining the error position and error evaluator polynomials includes: a zeroth step of storing in a storage unit first coefficient data R0i (0xe2x89xa6ixe2x89xa62t) as R02t=1, R0i=0 (0xe2x89xa6ixe2x89xa62txe2x88x921), second coefficient data R1i (0xe2x89xa6ixe2x89xa62txe2x88x921) as R1i=Si (0xe2x89xa6ixe2x89xa62txe2x88x921), a third coefficient B0i as B0i=0 (0xe2x89xa6ixe2x89xa6t), and a fourth coefficient B1i as B1i=0 (0xe2x89xa6ixe2x89xa6t), B10=1, a first step of determining degree N0 and highest degree coefficient Q0 of a first polynomial corresponding to the first coefficient data R0i and determining degree N1 and highest degree coefficient Q1 of a second polynomial corresponding to the second coefficient data R1i to store Q=Q0*(1/Q1) in the storage unit, a second step of determining a difference DN=N0xe2x88x92N1 between respective degrees of the first and second polynomials, a third step of exchanging, when the difference in degree DN is less than 0, respective values of the first and second coefficient data R0i and R1i and exchanging respective values of the third and fourth coefficients B0i and B1i to proceed to the first step, a fourth step of storing in the storage unit R1i=Q*R1(ixe2x88x92DN)(0xe2x89xa6ixe2x89xa62txe2x88x921) when (ixe2x88x92DN) for the second coefficient data is at least 0, and storing the second coefficient data R1i as 0 when the (ixe2x88x92DN) is negative, a fifth step of storing in the storage unit B1i=Q*B1(ixe2x88x92DN)(0xe2x89xa6ixe2x89xa6t) when (ixe2x88x92DN) for the fourth coefficient is not negative, and storing the fourth coefficient B1i as 0 when the (ixe2x88x92DN) is negative, a sixth step of performing for the first and second coefficient data an operation
R0i=R0i exor R1i (0xe2x89xa6ixe2x89xa62txe2x88x921)
R12t=0 and performing for the third and fourth coefficients an operation
B0i=B0i exor B1i (0xe2x89xa6ixe2x89xa6t), and a seventh step of exchanging, when the first polynomial represented by the first coefficient data R0i has its degree higher than t respective values of the first and second coefficient data R0i and R1i and exchanging respective values of the first and fourth coefficients B0i and B1i and to proceed to the first step.
In the step of performing error correction on received data, when the degree of the first polynomial is equal to or less than t, the error evaluator polynomial is the first polynomial and the error locator polynomial is a third polynomial represented by the third coefficient B0i to calculate the error position and the error amount.
The present invention has thus an advantage that the time required for error check can be shortened, without increase in the number of storage elements and the circuit scale, by shortening the access time to the storage element and concurrently performing error correction and error check.
Another advantage is that fast data processing is possible by descrambling data with errors corrected that is read from a data buffer thereby reduce accesses to the buffer memory approximately by one-half.
Still another advantage is that effective fast processing is possible by calculating a syndrome of an outer code by data which has not been descrambled and performing error correction by descrambled data to achieve the minimum access to the buffer memory.
A further advantage is that an error-correcting device achieving fast error-correction can be provided, that implements an Euclidean algorithm operation for determining an error locator polynomial and an error amount polynomial without increase in the circuit area and power consumption.
The foregoing and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.